// LeetCode 主站 Problem Nr. 21: 合并两个有序链表

/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
	输入：l1 = [1,2,4], l2 = [1,3,4]
	输出：[1,1,2,3,4,4]

示例 2：
	输入：l1 = [], l2 = []
	输出：[]

示例 3：
	输入：l1 = [], l2 = [0]
	输出：[0]

提示：
    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100
    l1 和 l2 均按 非递减顺序 排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"

	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	return method2(list1, list2)
}

// 重新构造节点
func method1(list1, list2 *ListNode) *ListNode {
	pointer1, pointer2 := list1, list2
	sentinel := &ListNode{}
	pointer := sentinel

	for pointer1 != nil && pointer2 != nil {
		if pointer1.Val >= pointer2.Val {
			pointer.Next = &ListNode{Val: pointer2.Val}
			pointer2 = pointer2.Next
			pointer = pointer.Next
		} else {
			pointer.Next = &ListNode{Val: pointer1.Val}
			pointer1 = pointer1.Next
			pointer = pointer.Next
		}
	}

	if pointer1 != nil {
		pointer.Next = pointer1
	}

	if pointer2 != nil {
		pointer.Next = pointer2
	}

	return sentinel.Next
}

// 调整节点的Next指针
func method2(list1, list2 *ListNode) *ListNode {
	pointer1, pointer2 := list1, list2
	sentinel := &ListNode{}
	pointer := sentinel

	for pointer1 != nil && pointer2 != nil {
		if pointer1.Val >= pointer2.Val {
			pointer.Next = pointer2
			pointer = pointer.Next
			pointer2 = pointer2.Next
		} else {
			pointer.Next = pointer1
			pointer = pointer.Next
			pointer1 = pointer1.Next
		}
	}

	if pointer1 != nil {
		pointer.Next = pointer1
	}

	if pointer2 != nil {
		pointer.Next = pointer2
	}

	return sentinel.Next
}

func main() {
	list1 := ds.BuildSinglyLinkedList([]int{1,2,4})
	list2 := ds.BuildSinglyLinkedList([]int{1,3,4})

	list3 := mergeTwoLists(list1, list2)
	fmt.Println(list3.ToList())
}
